1. Field of the Invention
The techniques described herein generally relate to microprocessors, and in particular to reducing power consumption for branch prediction.
2. Discussion of Related Art
Microprocessors are electronic devices that can perform a variety of computing operations in response to instructions that implement a computer program. A common technique for implementing computer programs is to send multiple instructions to the execution unit of the microprocessor in a predetermined sequence, and these instructions are then executed in sequential order. In some circumstances, program execution jumps out of order to execute an instruction which is not the next instruction in the sequence. One example of an instruction that causes the execution to jump out of sequence is a branch instruction. When a branch instruction is executed, the microprocessor can jump to the target instruction identified by the branch instruction, and the microprocessor executes the target instruction next, rather than the next sequential instruction.
By way of illustration, FIG. 1 shows one example of a program execution sequence in which five sequential instructions 1-5 are executed in a sequential manner, with instruction 1 being executed first, instruction 2 being executed second, etc. In this example, instruction 5 is a branch instruction that specifies instruction 2 as its target instruction. Upon executing branch instruction 5, the microprocessor jumps out of the sequential order of instructions to execute instruction 2 next in the order of program execution, rather than the next sequential instruction 6.
Microprocessors often process instructions using several stages, which can include an instruction fetch stage in which the instructions are fetched from an instruction cache, an instruction decode stage in which the fetched instructions are decoded, and an instruction execution stage in which the instruction is executed. To improve the speed at which multiple instructions are processed through the various stages, some microprocessors use a technique known as pipelining. Pipelining is analogous to an assembly line, in the sense that multiple stages of the pipeline concurrently perform different parts of the process on several different instructions. In one example of a pipelining technique, the first instruction 1 is processed by the first stage of the pipeline in a first computing cycle. In the second cycle, the first instruction 1 goes on to the second stage of the pipeline and the second instruction 2 begins the first stage of the pipeline. In the third cycle, the first instruction 1 proceeds to the third stage of the pipeline, the second instruction 2 proceeds to the second stage of the pipeline, and the third instruction 3 begins the first stage of the pipeline, etc. Pipelining can enable multiple instructions to be executed more quickly than would be the case if only one instruction were processed at a time by the microprocessor. For example, pipelining techniques may allow the processing of a different instruction to be completed in each cycle.
Branch instructions can reduce the efficiency of pipelining techniques. When a branch instruction is executed, the microprocessor may attempt to jump out of the sequential order to execute a target instruction that is not already in the pipeline. To jump to the target instruction, the microprocessor may discard the instructions that are already in the pipeline and re-start the pipeline beginning at the target instruction. As a consequence, a delay can occur while the target instruction is fetched and processed by the initial stages of the pipeline, causing an overall reduction in the speed at which instructions are processed through the pipeline.
Branch prediction is a technique that has been used to improve the speed of pipelined microprocessors that execute branch instructions. Branch prediction can increase the speed of pipelined microprocessors by enabling the microprocessor to fetch the instruction that is likely to be executed after a branch instruction, prior to executing the branch instruction. Branch prediction may involve predicting whether or not a conditional branch is taken, and/or predicting the branch target, which is the target instruction of the branch instruction. For example, when the microprocessor determines that a conditional branch is likely to be taken, the predicted target instruction may be fetched into the pipeline in advance of executing the branch instruction to prepare the pipeline for the branch operation.
A branch history table is a branch prediction unit that can store historical information about whether previous branches were taken, and this historical information can be used to predict whether future branches will be taken. A branch target buffer is a branch prediction unit that can predict the target of a branch instruction. Some microprocessors use both a branch history table and a branch target buffer to perform branch prediction.